package com.wm.algorithm.linked;

import com.wm.algorithm.linked.entity.ListNode;

import java.util.PriorityQueue;

/**
 * @ClassName:DifficultyLinked
 * @Description: 困难等级链表
 * @Author:Deamer
 * @Date:2022/2/3 20:44
 **/
public class DifficultyLinked {
    public static void main(String[] args) {
        ListNode head = new ListNode(5);
        head.next = new ListNode(4);
        head.next.next = new ListNode(3);
        head.next.next.next = new ListNode(2);
        head.next.next.next.next = new ListNode(1);
        ListNode tmpNode = head;
        System.out.println("转换之前：");
        while (head != null) {
            System.out.print(head.val + "\t");
            head = head.next;
        }
        ListNode newNode = null;
        System.out.println();
        System.out.println("转换之后：");
        while (newNode != null) {
            System.out.print(newNode.val + "\t");
            newNode = newNode.next;
        }
    }

    /**
     * 25. K 个一组翻转链表
     * https://leetcode.cn/problems/reverse-nodes-in-k-group/
     * 方法：递归+迭代
     * 思路：先反转head开头的k个元素；将第k+1个元素作为head递归调用reverseKGroup函数；将上面两个过程的结果连接起来
     *
     * @param head
     * @param k
     * @return
     */
    // O(n)/O(n)
    public ListNode reverseKGroup(ListNode head, int k) {
        if (head == null) {
            return null;
        }
        ListNode a = head, b = head;
        for (int i = 0; i < k; i++) {
            if (b == null) {
                return head;
            }
            b = b.next;
        }
        ListNode newHead = reverse(a, b);
        a.next = reverseKGroup(b, k);
        return newHead;
    }

    private ListNode reverse(ListNode a, ListNode b) {
        ListNode pre = null, cur = a, next = a;
        while (cur != b) {
            next = cur.next;
            cur.next = pre;

            pre = cur;
            cur = next;
        }
        return pre;
    }

    /**
     * 23. 合并K个升序链表
     * https://leetcode-cn.com/problems/merge-k-sorted-lists/
     * 方法三：使用优先队列合并
     * 用到优先级队列（二叉堆）这种数据结构，把链表节点放入一个最小堆，就可以每次获得 k 个节点中的最小节点
     *
     * @param lists
     * @return
     */
    // 时间复杂度：O(kn×logk) 空间复杂度：O(k)  k:数组长度 n:链表长度
    public static ListNode mergeKLists3(ListNode[] lists) {
        if (lists.length == 0) {
            return null;
        }
        // 虚拟头节点
        ListNode dummy = new ListNode(0);
        ListNode result = dummy;
        // 优先队列，最小堆
        PriorityQueue<ListNode> pq = new PriorityQueue<>(lists.length, (a, b) -> a.val - b.val);
        // 将k个链表的头节点加入最小堆中
        for (ListNode head : lists) {
            if (head != null) {
                pq.add(head);
            }
        }
        while (!pq.isEmpty()) {
            // 将最小节点接到结果链表中
            ListNode node = pq.poll();
            result.next = node;
            // 继续向队列中添加出队列元素的下一个元素
            if (node.next != null) {
                pq.add(node.next);
            }
            // 指针不断向后移动
            result = result.next;
        }
        return dummy.next;
    }

    /**
     * 23. 合并K个升序链表
     * https://leetcode-cn.com/problems/merge-k-sorted-lists/
     * 方法二：分治合并
     * 将首中合并的链表和中尾合并的链表合并
     *
     * @param lists
     * @return
     */
    // 时间复杂度：O(kn×logk) 空间复杂度：O(logk)  k:数组长度 n:链表长度
    public static ListNode mergeKLists2(ListNode[] lists) {
        return merge(lists, 0, lists.length - 1);
    }

    private static ListNode merge(ListNode[] lists, int leftIndex, int rightIndex) {
        if (leftIndex == rightIndex) {
            return lists[leftIndex];
        }
        if (leftIndex > rightIndex) {
            return null;
        }
        int mid = (leftIndex + rightIndex) >> 1;
        return mergeTwoLists(merge(lists, leftIndex, mid), merge(lists, mid + 1, rightIndex));
    }

    /**
     * 23. 合并K个升序链表
     * https://leetcode-cn.com/problems/merge-k-sorted-lists/
     * 方法一：顺序合并
     * 每次的结果和下一个链表合并
     *
     * @param lists
     * @return
     */
    // 时间复杂度：O(n) 空间复杂度：O(1)
    public static ListNode mergeKLists(ListNode[] lists) {
        ListNode mergeNode = null;
        for (int i = 0; i < lists.length; i++) {
            mergeNode = mergeTwoLists(mergeNode, lists[i]);
        }
        return mergeNode;
    }

    // 合并两个有序链表
    private static ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        if (list1 == null || list2 == null) {
            return list1 == null ? list2 : list1;
        }
        ListNode result = new ListNode(0);
        ListNode node = result;
        while (list1 != null && list2 != null) {
            if (list1.val < list2.val) {
                node.next = list1;
                list1 = list1.next;
            } else {
                node.next = list2;
                list2 = list2.next;
            }
            node = node.next;
        }
        node.next = list1 == null ? list2 : list1;
        return result.next;
    }
}
